import taichi as ti
import numpy as np
import time
n2 = 25
n = 2**n2
print('n=', n)
ti.init(ti.opengl)


value = ti.field(ti.f32, n)
step = ti.field(ti.i32, 2)  #包含内步长与外步长

step[0] = 2  #外步长
step[1] = 2  #内步长

@ti.kernel
def init():
    for i in range(n):
        value[i]=ti.random(ti.f32)


@ti.func
def xor(a, b):
    return (a + b) & 1


@ti.kernel
def getResult():
    for i in range(n):
        result[i] = value[num[i]]


@ti.kernel
def step1():
    for i in range(n // 2):
        stepLength=ti.Vector([step[0],step[1]])
        halfstep = stepLength[1] // 2
        i1 = i + (i // (halfstep)) * halfstep
        i2 = i1 + halfstep
        a, b = value[i1], value[i2]
        updown = (i * 2 // stepLength[0]) & 1  #up,down方向
        if xor(a > b, updown):
            value[i1], value[i2] = b, a



init()
rand=value.to_numpy()
print('initial finish')
print('steps:',step[0], step[1])
step1()
t1=time.time()
for i in range(1, n2 + 1):
    step[0] = 2**i
    for j in range(i):
        step[1] = 2**(i - j)
        step1()
        #print(step[0], step[1])
print('min:',value[0])
t2=time.time()
print('ti bisort time:',t2-t1,'s')
print('ti bisort result:',value)
t1=time.time()
rand.sort(kind='quicksort')
print('np result',rand)
t2=time.time()
print('np quicksort time:',t2-t1,'s')
input('enter to continue')

